SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Min-conflicts algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Min-conflicts algorithm</span></span>

</h1>

</header>

<p>In <a href="Computer_science" title="Computer science">computer science</a>, a <b>min-conflicts algorithm</b> is a <a href="Search_algorithm" title="Search algorithm">search algorithm</a> or heuristic method to solve <a href="Constraint_satisfaction_problem" title="Constraint satisfaction problem">constraint satisfaction problems</a>.

</p><p>One such algorithm is <b>min-conflicts hill-climbing</b>.<sup id="cite_ref-Minton90_1-0" class="reference"><a href="#cite_note-Minton90-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Given an initial assignment of values to all the variables of a constraint satisfaction problem (with one or more constraints not satisfied), select a variable from the set of variables with conflicts violating one or more of its constraints. Assign to this variable a value that minimizes the number of conflicts (usually breaking ties randomly). Repeat this process of conflicted variable selection and min-conflict value assignment until a solution is found or a pre-selected maximum number of iterations is reached. If a solution is not found the algorithm can be restarted with a different initial assignment.

</p><p>Because a constraint satisfaction problem can be interpreted as a <a href="Local_search_(optimization)" title="Local search (optimization)">local search problem</a> when all the variables have an assigned value (called a complete state), the min conflicts algorithm can be seen as a repair <a href="Heuristic_(computer_science)" title="Heuristic (computer science)">heuristic</a><sup id="cite_ref-Minton92_2-0" class="reference"><a href="#cite_note-Minton92-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> that chooses the state with the minimum number of conflicts.

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

<pre><b>algorithm</b> MIN-CONFLICTS <b>is</b>

<b>input:</b> console.<i>csp</i>, A constraint satisfaction problem.

<i>max_steps</i>, The number of steps allowed before giving up.

<i>current_state</i>, An initial assignment of values for the variables in the csp.

<b>output:</b> A solution set of values for the variable <b>or</b> <i>failure</i>.

<b>for</b> i ← 1 <b>to</b> max_steps <b>do</b>

<b>if</b> <i>current_state</i> is a solution of <i>csp</i> <b>then</b>

<b>return</b> <i>current_state</i>

<b>set</b> <i>var</i> ← a randomly chosen variable from the set of conflicted variables CONFLICTED[<i>csp</i>]

<b>set</b> <i>value</i> ← the value v for <i>var</i> that minimizes CONFLICTS(<i>var</i>,<i>v</i>,<i>current_state</i>,<i>csp</i>)

<b>set</b> <i>var</i> ← <i>value</i> in <i>current_state</i>

<b>return</b> <i>failure</i>

</pre>

<p>Although not specified in the algorithm, a good initial assignment can be critical for quickly approaching a solution. Use a <a href="Greedy_algorithm" title="Greedy algorithm">greedy algorithm</a> with some level of randomness and allow variable assignment to break constraints when no other assignment will suffice. The randomness helps min-conflicts avoid local minima created by the greedy algorithm's initial assignment. In fact, Constraint Satisfaction Problems that respond best to a min-conflicts solution do well where a greedy algorithm almost solves the problem. <a href="Map_coloring" title="Map coloring">Map coloring</a> problems do poorly with Greedy Algorithm as well as Min-Conflicts. Sub areas of the map tend to hold their colors stable and min conflicts cannot hill climb to break out of the local minimum. The <style data-mw-deduplicate="TemplateStyles:r886049734">

/* start https://en.wikipedia.org/ */

.mw-parser-output .monospaced{font-family:monospace,monospace}

/* end https://en.wikipedia.org/ */

</style><span class="monospaced">CONFLICTS</span> function counts the number of constraints violated by a particular object, given that the state of the rest of the assignment is known.

</p>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

<p>Although Artificial Intelligence and <a href="Discrete_optimization" title="Discrete optimization">Discrete Optimization</a> had known and reasoned about Constraint Satisfaction Problems for many years, it was not until the early 1990s that this process for solving large CSPs had been codified in algorithmic form. Early on, Mark Johnston of the <a href="Space_Telescope_Science_Institute" title="Space Telescope Science Institute">Space Telescope Science Institute</a> looked for a method to schedule astronomical observations on the <a href="Hubble_Space_Telescope" title="Hubble Space Telescope">Hubble Space Telescope</a>. In collaboration with Hans-Martin Adorf of the <a href="Space_Telescope_European_Coordinating_Facility" title="Space Telescope European Coordinating Facility">Space Telescope European Coordinating Facility</a>, he created a neural network capable of solving a toy <i>n</i>-queens problem (for 1024 queens).<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> Steven Minton and Andy Philips analyzed the neural network algorithm and separated it into two phases: (1) an initial assignment using a greedy algorithm and (2) a conflict minimization phases (later to be called "min-conflicts"). A paper was written and presented at AAAI-90; Philip Laird provided the mathematical analysis of the algorithm.

</p><p>Subsequently, Mark Johnston and the STScI staff used min-conflicts to schedule astronomers' observation time on the Hubble Space Telescope.

</p>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

<p>Min-Conflicts solves the <i>N</i>-Queens Problem by selecting a column from the chess board for queen reassignment. The algorithm searches each potential move for the number of conflicts (number of attacking queens), shown in each square. The algorithm moves the queen to the square with the minimum number of conflicts, breaking ties randomly. Note that the number of conflicts is generated by each new direction that a queen can attack from. If two queens would attack from the same direction (row, or diagonal) then the conflict is only counted once. Also note that if a queen is in a position in which a move would put it in greater conflict than its current position, it does not make a move. It follows that if a queen is in a state of minimum conflict, it does not have to move.

</p><p>This algorithm's performance depends greatly on the choice of starting position. A good starting position can be generated by assigning queens column by column with each assignment being to a row that minimizes the number of constraint violations. This results in a starting position with an average number of constraint violations that is surprisingly small and grows very slowly with <i>n</i> (e.g. 12.8 for n=10<sup>6</sup>).

</p><p>Given a good starting position, the number of reassignments required for a solution is similarly constant: this algorithm will even solve the million-queens problem in approximately 50 reassignments. The number of constraint evaluations for each reassignment grows with <i>n</i> leading to nearly linear run-time.

</p><p>This discovery and observations led to a great amount of research in 1990 and began research on local search problems and the distinctions between easy and hard problems. <i>N</i>-Queens is easy for local search because solutions are densely distributed throughout the state space. It is also effective for hard problems. For example, it has been used to schedule observations for the <a href="Hubble_Space_Telescope" title="Hubble Space Telescope">Hubble Space Telescope</a>, reducing the time taken to schedule a week of observations from three weeks to around 10 minutes.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="Warnsdorff's_algorithm" class="mw-redirect" title="Warnsdorff's algorithm">Warnsdorff's algorithm</a></li>

<li><a href="Eight_queens" class="mw-redirect" title="Eight queens">Eight queens Puzzle</a></li>

<li><a href="Guided_Local_Search" class="mw-redirect" title="Guided Local Search">Guided Local Search</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFMintonMark_D._JohnstonAndrew_B._PhilipsPhilip_Laird1990" class="citation journal cs1">Minton, Steven; Mark D. Johnston; Andrew B. Philips; Philip Laird (1990). <a rel="nofollow" class="external text" href="http://www.aaai.org/Papers/AAAI/1990/AAAI90-003.pdf">"Solving Large-Scale Constraint Satisfaction and Scheduling Problems Using a Heuristic Repair Method"</a> <span class="cs1-format">(PDF)</span>. <i>Eighth National Conference on Artificial Intelligence (AAAI-90), Boston, Massachusetts</i>: <span class="nowrap">17–</span>24<span class="reference-accessdate">. Retrieved <span class="nowrap">27 March</span> 2013</span>.</cite></span>

</li>

<li id="cite_note-Minton92-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-Minton92_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFMintonMark_D._JohnstonAndrew_B._PhilipsPhilip_Laird1992" class="citation journal cs1">Minton, Steven; Mark D. Johnston; Andrew B. Philips; Philip Laird (1992). <a rel="nofollow" class="external text" href="http://pdf.aminer.org/000/745/527/minimizing_conflicts_a_heuristic_repair_method_for_constraint_satisfaction_and.pdf">"Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems"</a> <span class="cs1-format">(PDF)</span>. <i>Artificial Intelligence</i>. <b>58</b> (1): <span class="nowrap">161–</span>205. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.308.6637">10.1.1.308.6637</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0004-3702%2892%2990007-k">10.1016/0004-3702(92)90007-k</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14830518">14830518</a><span class="reference-accessdate">. Retrieved <span class="nowrap">27 March</span> 2013</span>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFJohnstonAdorf1989" class="citation journal cs1">Johnston, M. D.; Adorf, H.-M. (1989). "Learning in Stochastic Neural Networks for Constraint Satisfaction Problems". <i>NASA Conf. On Space Telerobotics 1989, Pasadena, CA; G. Rodriguez, H. Seraji (Eds.)</i>: 367–376 vol.II.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFAdorfJohnston1990" class="citation book cs1">Adorf, H.-M.; Johnston, M. D. (1990). "A discrete stochastic neural network algorithm for constraint satisfaction problems". <i>1990 IJCNN International Joint Conference on Neural Networks</i>. pp. 917–924 vol.3. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FIJCNN.1990.137951">10.1109/IJCNN.1990.137951</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:26917432">26917432</a>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text">Stuart Russell, Peter Norvig, “Artificial Intelligence: A Modern Approach (3rd Edition)”, pp. 220-222, December 11, 2009.</span>

</li>

</ol></div></div>

<ul><li><a href="Stuart_J._Russell" title="Stuart J. Russell">Stuart J. Russell</a> and <a href="Peter_Norvig" title="Peter Norvig">Peter Norvig</a>, <i><a href="Artificial_Intelligence%3A_A_Modern_Approach" title="Artificial Intelligence: A Modern Approach">Artificial Intelligence: A Modern Approach</a></i></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external autonumber" href="http://catalogue.nla.gov.au/Record/4057689">[1]</a> The min-conflicts heuristic microform : experiment and theoretical results / Steven Minton ... [et al.]. NASA, Ames Research Center, Artificial Intelligence Research Branch. Distributed to depository libraries in microfiche.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-09-04" href="https://en.wikipedia.org/wiki/?title=Min-conflicts_algorithm&oldid=1244012152">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>